package com.hjr.leetcode.question100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 30. 串联所有单词的子串
 * 给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。
 * <p>
 * s 中的 串联子串 是指一个包含  words 中所有字符串以任意顺序排列连接起来的子串。
 * <p>
 * 例如，如果 words = ["ab","cd","ef"]， 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。
 * 返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。
 */
public class q30 {

    public static void main(String[] args) {
        System.out.println(findSubstring("barfoothefoobarman", new String[]{"foo","bar"}));
    }

    //回溯算法、暴力算法
    public static List<Integer> findSubstring(String s, String[] words) {
        //先遍历所有子串
        List<String> list = new ArrayList<>();
        //只能回溯算法
        backTracking(words, list, new boolean[words.length], new StringBuffer());

        ArrayList<Integer> result = new ArrayList<>();

        for (String str : list) {
            findSubstring2(s, str, result);
        }

        return result.stream().distinct().toList();
    }

    private static void findSubstring2(String s, String words, List<Integer> result) {
        if (!s.contains(words)){
            return;
        }
        while (s.contains(words)){
            result.add(s.indexOf(words));
            String left = s.substring(0, s.indexOf(words));
            String right = s.substring(s.indexOf(words) + words.length());
            findSubstring2(left, words, result);
            findSubstring2(right, words, result);
            if (left.length() > right.length()){
                s = left;
            }else {
                s = right;
            }
        }
    }

    private static void backTracking(String[] words, List<String> list, boolean[] used, StringBuffer stringBuffer) {
        if (stringBuffer.length() == words.length * words[0].length()) {
            list.add(stringBuffer.toString());
            return;
        }

        for (int i = 0; i < words.length; i++) {
            if (!used[i]) {
                used[i] = true;
                stringBuffer.append(words[i]);
                backTracking(words, list, used, stringBuffer);
                stringBuffer.delete(stringBuffer.length() - words[i].length(), stringBuffer.length());
                used[i] = false;
            }
        }

    }
}
